1. Field of the Invention
The present invention pertains to the field of high speed digital data processors and, more particularly, to a method of synchronizing access to shared data in a multiprocessor system.
2. Background Information
Communication costs are an important factor in the efficiency of multiprocessor data processing systems. In systems with large numbers of processors, such as massively parallel architectures, communication costs can be of critical importance. Communication costs arise not only from the time required for a single communication but also from the number of interprocessor communications required to synchronize processors sharing data. It is therefore important in a multiprocessor system to minimize both the cost of a single communication and the number of communications.
It is well-known in the art to use a lock mechanism to synchronize processors sharing data. A lock mechanism restricts access to a shared data memory location by access to the location unless the processor has access rights. In one well-known lock mechanism, a semaphore bit is used to protect each shared data memory location. In such a system, a logic "one" written to the semaphore bit is a signal to other processors that data at the protected memory location is being modified. Before attempting access, a processor will read the semaphore bit for a desired shared data memory location. If the bit is set, the processor waits until the semaphore bit is cleared. Once the bit is cleared, the processor sets the semaphore bit and accesses the shared data memory location. After the processor finishes updating the memory location with a new value, the semaphore bit is cleared to allow access to the data by other processors.
The use of semaphores increases communication costs by requiring at least two memory references for each shared data memory access, one to the semaphore memory and one to the shared data memory location. In large-scale or massively parallel multiprocessor system, this communication overhead can be prohibitively expensive. For instance, in shared memory multiprocessing systems based on either k-ary n-cubes (or in networks such as rings, meshes, tori, binary n-cubes and Omega networks which are isomorphic to k-ary n-cubes) where memory access time increases with the number of node connections between the requesting processor and the memory on any particular node, doubling the number of references needed to retrieve the contents of a memory location can result in unacceptable delay. Processors in this class of topologies communicate via a message passing protocol in which information intended for a distant processor is packetized and routed through intermediate processors to the destination processor. Therefore, a memory request must pass through a series on nodes on the way to the memory location and the memory data must repeat the journey in reverse to complete the transaction. The requirement of two such transactions for each shared data access is unacceptable.
It is clear that there is a need for a method of synchronizing accesses to shared data in a multiprocessing system which reduces the communication overhead associated with semaphore controlled systems.